/**
 * @param {string[]} words
 * @return {string[]}
 */

class TrieNode {
    chilren: TrieNode[] = new Array(26)
    isEnd: boolean = false

}


const A = 'a'.charCodeAt(0)


const toBytes = (w: string) => w.split('').map(c => c.charCodeAt(0) - A)

var findAllConcatenatedWordsInADict = function (words: string[]) {

    const root = new TrieNode()

    for (const w of words) {
        const bytes = toBytes(w)

        let p = root
        for (const b of bytes) {
            p.chilren[b] = p.chilren[b] || new TrieNode()
            p = p.chilren[b]
        }
        p.isEnd = true
    }


    const res = []
    for (const w of words) {
        if (test(toBytes(w), 0, 0)) {
            res.push(w)
        }
    }

    return res

    function test(bytes: number[], i: number, c: number) {


        let p = root
        while (i < bytes.length) {
            const byte = bytes[i]

            if (!p.chilren[byte]) {
                return false
            } else {
                if (p.chilren[byte].isEnd) {

                    if (i === bytes.length - 1) {
                        return c + 1 >= 2
                    }

                    if (test(bytes, i + 1, c + 1)) {
                        return true
                    }

                }
            }

            p = p.chilren[byte]

            i++;
        }

        return false
    }
};


console.log(findAllConcatenatedWordsInADict(["cat", "dog", "catcat"]))
console.log(findAllConcatenatedWordsInADict(["cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"]))